/* 判断二叉树是否为完全二叉树 */

#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 判断是否是完全二叉树
bool fun(BTNode *p)
{
  // 创建队列
  BTNode *q[maxsize];
  int front = 0, rear = 0;
  
  // 如果二叉树为空
  if (p == NULL)
    return true; // 属于完全二叉树
  
  // 根结点进队
  q[++rear] = p;
  
  // 层次遍历
  while (front != rear)
  {
    // 结点出队
    p = q[++front];
    
    // 如果结点不为空 -- 左右孩子都进队
    if (p != NULL)
    {
      q[++rear] = p->lchild;
      q[++rear] = p->rchild;
    }
    
    // 否则
    else
      while (front != rear) // 判断队列是否全是NULL
      {
        p = q[++front];
        if (p != NULL)
          return false; // 如果不是，则不是完全二叉树
      }
  }
  
  // 是完全二叉树
  return true;
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 判断是否是完全二叉树
  if (fun(T))
    cout << "是完全二叉树!";
  else
    cout << "不是完全二叉树!";
  return 0;
}
